1. Field of the Invention
This invention relates to techniques for converting representations of digital circuits, such as logic diagrams or schematics, into layouts for circuit implementation, and more specifically to the identification of logic input equivalences for controlling and optimizing circuit area and circuit delays during the layout process.
2. Description of the Prior Art
Many very sophisticated logic synthesis and layout tools have been developed for producing circuit layouts from circuit and logic diagrams. One recent article, xe2x80x9cEffective Coupling between Logic Synthesis and Layout Tools for Synthesis of Area and Speed-Efficient Circuitsxe2x80x9d, Chandrasekhar, McCharles and Wallace, published in VLSI DESIGN, 1997, Vol. 5, No. 2, pp. 125-140, co-authored by the inventor hereof, proposes coupling between logic synthesis and layout tools to improve post-layout circuit implementation.
As noted in that article, many circuits synthesized by automatic logic synthesis or other methods contain internal nodes at the outputs of logic gates that implement the same logic function and are therefore logically equivalent. Such nodes are considered output equivalent and techniques are provided for exploiting output equivalents during the layout of digital circuits. Similarly, input equivalence is demonstrated in logic circuits in which the output of an output gate does not change even if the circuit configuration is changed by interchanging the drivers connected to input gates feeding that output gate, as shown in FIG. 8 of that article.
Although techniques are provided for working with output equivalence, what are needed are techniques for identifying and exploiting input equivalences in the synthesis and layout of digital logic circuits.
The present invention provides improved techniques for identifying input equivalence in digital circuits for use, for example, in swapping pins in order to modify circuit layout. These techniques include the steps of decomposing the circuit into one or more fanout-free regions (FFRs), generating quasi-canonical models to create a swap structure, identifying pin swap groups and swapping pins as desired for final layout or configuration.
The present invention proceeds by looking for extensible symmetric logic functions (such as AND, OR, and XOR functions) within and between gates in a logic circuit. Such functions are grown backwards as long as they can continue to be extended and then analyzed to identify input equivalences to identify permutable pins.
The present invention be conveniently implemented in a computer by coding appropriate software on computer coded media or by any other conventional means of programming a computer. The required software may be written by a person of ordinary skill in the art of developing programs for analyzing digital circuits for layout and similar operations.
In a first aspect, the present invention provides a method of analyzing a digital circuit to identify input equivalences by decomposing the digital circuit into one or more regions having a first set of specified characteristics, creating a modified circuit structure from the decomposed regions, and identifying pin swap groups within the modified circuit structure.
In another aspect, the present invention provides a method of analyzing a digital circuit to identify input equivalences by decomposing the digital circuit into one or more fanout-free regions, creating a quasi-canonical circuit structure from the fanout-free regions, and identifying pin swap groups within the circuit structure.
These and other features and advantages of this invention will become further apparent from the detailed description and accompanying figures that follow. In the figures and description, numerals indicate the various features of the invention, like numerals referring to like features throughout both the drawings and the description.